package com.demo101_检查二叉树是否对称;

import java.util.ArrayList;

/**
 * 不过这样还是有问题的, 因为这个可能存在这个 虽然不对称,但是结果仍然是 对称的情况
 */
class TreeNode {
    int val;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

}
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return false;
        }
        TreeNode pr=root.right;
        TreeNode pl=root.left;

        //定义一个前序遍历
        ArrayList<Integer> leftList = new ArrayList<>();
        ArrayList<Integer> rightList = new ArrayList<>();
        dfsl(pl,leftList);
        dfsr(pr,rightList);

        if (rightList.size()!= leftList.size()){
            return false;
        }
        for (int i = 0; i < rightList.size(); i++) {
            if (rightList.get(i)!=leftList.get(i)){
                return false;
            }
        }

        return true;
    }

    private void dfsr(TreeNode pr, ArrayList<Integer> rightList) {
        if (pr==null){
            return;
        }
        dfsr(pr.right,rightList);
        rightList.add(pr.val);
        dfsr(pr.left,rightList);
    }

    private void dfsl(TreeNode pl, ArrayList<Integer> leftList) {
        if (pl==null){
            return;
        }
        dfsl(pl.left,leftList);
        leftList.add(pl.val);
        dfsl(pl.right,leftList);
    }
}
